---
title: "trie变形 存二进制位"
created: 2025-11-28
tags:
  - 算法
---

# trie变形 存二进制位

## 题目 [最大异或对](https://www.acwing.com/problem/content/145/)

![[image-26f3af98.png]]

## 思路分析

![[image-44dfb024.png]]

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=100010,M=3100010;//一个int最多31位 所以结点最大为31*N

int a[N],son[M][2];//孩子顶多两个 0或1

int idx;

void insert(int x)

{

    int p=0;//思路一样 从根节点开始

    for(int i=30;i>=0;i--)

    {

        int u=x>>i&1;//由左到右取每位

        if(!son[p][u])

            son[p][u]=++idx;

        p=son[p][u];

    }

}

int search(int x)

{

    int p=0,res=0;

    for(int i=30;i>=0;i--)

    {

        int u=x>>i&1;

        if(son[p][!u])//理想情况存在

        {

             res=res*2+1;//左移一位且该位为1

             p=son[p][!u];

        }

        else

        {

            res=res*2+0;//左移一位且该位为0

            p=son[p][u];

        }

    }

    return res;

}

int main()

{

    int n;

    cin>>n;

    for(int i=0;i<n;i++)

    {

        scanf("%d",&a[i]);

        //预想是在插入前先查询 但是为了减少边界情况的判断（第一次没有）

        //就先插入 再查询 其实不会影响结果 自己和自己异或的结果是0

        insert(a[i]);

    }

    int res=0;

    for(int i=0;i<n;i++)

        res=max(res,search(a[i]));//结果用res维护 找到更大的再更新

    cout<<res<<endl;

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[2-Learning/02-算法/02-听课板子/数据结构/trie树/trie树|trie树]] 🏠 [[00-听课板子]] ➡️ [[并查集|并查集]]